import com.sun.xml.internal.fastinfoset.algorithm.BooleanEncodingAlgorithm;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/5
 * \* Time: 17:45
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class BST相关操作 {
    /**
     * 二叉树结构定义
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * BST类型题目的框架
     * @param root
     * @param target
     */
    void BST(TreeNode root, int target) {
        if (root.val == target){
            // 找到目标，做点什么
        }

        if (root.val < target){
            BST(root.right, target);
        }
        if (root.val > target){
            BST(root.left, target);
        }
    }

    /**
     * 判断BST的合法性
     * @param root
     * @param min
     * @param max
     * @return
     */
    boolean isValidBST(TreeNode root,TreeNode min,TreeNode max){
        //base case
        if(root==null){
            return true;
        }
        //若root.val不符合max和min的限制则返回false
        if(min!=null&&root.val<=min.val){
            return false;
        }
        if(max!=null&&root.val>=max.val){
            return false;
        }
        //限定左子树的最大值是root.val，右子树的最小值是root.val
        return isValidBST(root.left,min,root)
                &&isValidBST(root.right,root,max);
    }

    boolean isValidBST(TreeNode root){
        return isValidBST(root,null,null);
    }

    /**
     * 寻找BST里的某个数，不存在就返回-1
     * @param root
     * @param target
     * @return
     */
    int searchBST(TreeNode root, int target){
        if(root==null){
            return -1;
        }
        if(root.val==target){
            return root.val;
        }
        if(root.val<target){
            return searchBST(root.right,target);
        }
        return searchBST(root.left,target);
    }

    /**
     * 在BST中插入元素
     * @param root
     * @param val
     * @return
     */
    TreeNode insertIntoBST(TreeNode root,int val){
        if(root==null){
            return new TreeNode(val);
        }
        if(root.val<val){
            root.right=insertIntoBST(root.right,val);
        }
        if(root.val>val){
            root.left=insertIntoBST(root.left,val);
        }
        return root;
    }

    /**
     * 在BST中删除元素
     * @param root
     * @param val
     * @return
     */
    TreeNode deleteNodeInBST(TreeNode root,int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            //A 恰好是末端节点，两个子节点都为空，那么它可以当场去世了。
            if(root.left==null&&root.right==null){
                return null;
            }
            //A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。
            if(root.left==null){
                return root.right;
            }
            if(root.right==null){
                return root.left;
            }
            // A 有两个子节点，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。
            TreeNode minNode = getMin(root.right);
            //将要删除的节点的值更换为右子树最小节点的值，然后删除右子树最小节点
            root.val = minNode.val;
            root.right = deleteNodeInBST(root.right, minNode.val);
        } else if (root.val > val) {
            root.left = deleteNodeInBST(root.left, val);
        } else if (root.val < val) {
            root.right = deleteNodeInBST(root.right, val);
        }
        return root;
    }

    TreeNode getMin(TreeNode node) {
        // BST 最左边的就是最小的
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }


}